{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #最小矩形面积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #geometry #array #math #combinatorics #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #几何 #数组 #数学 #组合数学 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minRecSize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小矩形面积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "二维平面上有 $N$ 条直线，形式为 `y = kx + b`，其中 `k`、`b`为整数 且 `k > 0`。所有直线以 `[k,b]` 的形式存于二维数组 `lines` 中，不存在重合的两条直线。两两直线之间可能存在一个交点，最多会有 $C_N^2$ 个交点。我们用一个平行于坐标轴的矩形覆盖所有的交点，请问这个矩形最小面积是多少。若直线之间无交点、仅有一个交点或所有交点均在同一条平行坐标轴的直线上，则返回0。\n",
    "\n",
    "注意：返回结果是浮点数，与标准答案 **绝对误差或相对误差** 在 10^-4 以内的结果都被视为正确结果\n",
    "\n",
    "\n",
    "**示例 1：**\n",
    "> 输入：`lines = [[2,3],[3,0],[4,1]]`\n",
    ">\n",
    "> 输出：`48.00000`\n",
    ">\n",
    "> 解释：三条直线的三个交点为 (3, 9) (1, 5) 和 (-1, -3)。最小覆盖矩形左下角为 (-1, -3) 右上角为 (3,9)，面积为 48\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    "> 输入：`lines = [[1,1],[2,3]]`\n",
    ">\n",
    "> 输出：`0.00000`\n",
    ">\n",
    "> 解释：仅有一个交点 (-2，-1）\n",
    "\n",
    "\n",
    "**限制：**\n",
    "+ `1 <= lines.length <= 10^5 且 lines[i].length == 2`\n",
    "+ `1 <= lines[0] <= 10000`\n",
    "+ `-10000 <= lines[1] <= 10000`\n",
    "+ `与标准答案绝对误差或相对误差在 10^-4 以内的结果都被视为正确结果`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [zui-xiao-ju-xing-mian-ji](https://leetcode.cn/problems/zui-xiao-ju-xing-mian-ji/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [zui-xiao-ju-xing-mian-ji](https://leetcode.cn/problems/zui-xiao-ju-xing-mian-ji/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,3],[3,0],[4,1]]', '[[1,1],[2,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "#         n = len(lines)\n",
    "#         if n < 2:return 0\n",
    "#         # 上下左右\n",
    "#         res = [-float('Inf'),float('Inf'),float('Inf'),-float('Inf')]\n",
    "#         for i in range(n):\n",
    "#             k,b = lines[i][0],lines[i][1]\n",
    "#             for j in range(i+1,n):\n",
    "#                 k1,b1 = lines[j][0],lines[j][1]\n",
    "#                 if k1 == k:\n",
    "#                     continue\n",
    "#                 x,y = 0,0\n",
    "#                 if b1 == b:\n",
    "#                     x,y = 0,b\n",
    "#                 else:\n",
    "#                     x = -(b1 - b)/(k1 - k)\n",
    "#                     y = x*k + b\n",
    "#                 print([x,y])\n",
    "#                 if res[0] < y:res[0] = y\n",
    "#                 if res[1] > y:res[1] = y\n",
    "#                 if res[2] > x:res[2] = x\n",
    "#                 if res[3] < x:res[3] = x\n",
    "#         if res[0] == res[1] or res[2] == res[3]:return 0\n",
    "#         if res[0] < 0 or res[3] < 0:return 0\n",
    "#         return (res[0] - res[1])*(res[3]-res[2])\n",
    "\n",
    "############################### 解法一 #################################\n",
    "# 先按照斜率k和b从小到大排序 （时间nlogn）\n",
    "# 再按照斜率的不同分为m组, 每组只有同一斜率最小的b和最大的b（m <= n, 时间n, 空间m~n）\n",
    "# 对m组进行遍历，每一组和上一组进行计算，(时间m~n) 可以证明：\n",
    "# 每次更新右上方角点时，只计算本组最下方和上一组最上方的直线的交点做更新即可\n",
    "# 每次更新左下方角点时，只计算本组最上方和上一组最下方的直线的交点做更新即可\n",
    "# 理论时间O(nlogn + m), 空间O(m)\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        # 求交点的子函数\n",
    "        def getIntersect(line1, line2):\n",
    "            x = (line2[1] - line1[1])/(line1[0] - line2[0])\n",
    "            y = line1[0] * x + line1[1]\n",
    "            return (x, y)\n",
    "        # 按照斜率k和b从小到大排序, 若不多于2条直线返回0\n",
    "        n = len(lines)\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        lines.sort(key=lambda x:(x[0], x[1]))\n",
    "\n",
    "        # 按照斜率的不同分为m组分为m组\n",
    "        # minLines/maxLines记录某一斜率直线组中b最小/大的直线（最上方/最下方的直线）\n",
    "        minLines = [lines[0]] # 某一斜率中b最小的直线\n",
    "        maxLines = [] # 某一斜率中b最大的直线\n",
    "        for i in range(1, n):\n",
    "            if lines[i][0] != lines[i-1][0]:\n",
    "                maxLines.append(lines[i-1])\n",
    "                minLines.append(lines[i])\n",
    "        maxLines.append(lines[-1])\n",
    "\n",
    "        # 若只有1组，则表明全为平行线\n",
    "        m = len(minLines)\n",
    "        if m <= 1:\n",
    "            return 0\n",
    "\n",
    "        # 右上方角点为（maX, maY), 左下方角点为（miX, miY)\n",
    "        maX, miX, maY, miY = -inf, inf, -inf, inf\n",
    "        for i in range(1, m):\n",
    "            # 每次更新右上方角点时，只计算本组最下方和上一组最上方的直线的交点做更新即可\n",
    "            x, y = getIntersect(minLines[i], maxLines[i-1])\n",
    "            maX = max(x, maX)\n",
    "            maY = max(y, maY) \n",
    "            # 每次更新左下方角点时，只计算本组最上方和上一组最下方的直线的交点做更新即可\n",
    "            x, y = getIntersect(maxLines[i], minLines[i-1])\n",
    "            miX = min(x, miX)\n",
    "            miY = min(y, miY)\n",
    "        return (maX-miX) * (maY - miY)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        if len(lines)<3: return 0\n",
    "\n",
    "        ks=dict()\n",
    "        kk=set()\n",
    "        for k,b in lines:\n",
    "            kk.add(k) \n",
    "            if k not in ks:\n",
    "                ks[k]=[b]\n",
    "            else:\n",
    "                ks[k].append(b)\n",
    "                if len(ks[k])>=2:\n",
    "                    ks[k]=[min(ks[k]),max(ks[k])]\n",
    "\n",
    "        kk=list(kk)\n",
    "        if len(kk)<2: return 0\n",
    "        kk.sort() \n",
    "        xmin,ymin,xmax,ymax=inf,inf,-inf,-inf\n",
    "        for i in range(1,len(kk)):\n",
    "            for b1 in ks[kk[i]]:\n",
    "                j=i-1\n",
    "                k1,k2=kk[i],kk[j]\n",
    "                for b2 in ks[kk[j]]:                    \n",
    "                    x,y=(b2-b1)/(k1-k2),(k1*b2-k2*b1)/(k1-k2)\n",
    "                    xmax,xmin,ymax,ymin=max(xmax,x),min(xmin,x),max(ymax,y),min(ymin,y)\n",
    "        return (xmax-xmin)*(ymax-ymin)      \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "############################### 解法一 #################################\n",
    "# 先按照斜率k和b从小到大排序 （时间nlogn）\n",
    "# 再按照斜率的不同分为m组, 每组只有同一斜率最小的b和最大的b（m <= n, 时间n, 空间m~n）\n",
    "# 对m组进行遍历，每一组和上一组进行计算，(时间m~n) 可以证明：\n",
    "# 每次更新右上方角点时，只计算本组最下方和上一组最上方的直线的交点做更新即可\n",
    "# 每次更新左下方角点时，只计算本组最上方和上一组最下方的直线的交点做更新即可\n",
    "# 理论时间O(nlogn + m), 空间O(m)\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        # 求交点的子函数\n",
    "        def getIntersect(line1, line2):\n",
    "            x = (line2[1] - line1[1])/(line1[0] - line2[0])\n",
    "            y = line1[0] * x + line1[1]\n",
    "            return (x, y)\n",
    "        # 按照斜率k和b从小到大排序, 若不多于2条直线返回0\n",
    "        n = len(lines)\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        lines.sort(key=lambda x:(x[0], x[1]))\n",
    "\n",
    "        # 按照斜率的不同分为m组分为m组\n",
    "        # minLines/maxLines记录某一斜率直线组中b最小/大的直线（最上方/最下方的直线）\n",
    "        minLines = [lines[0]]\n",
    "        maxLines = []\n",
    "        for i in range(1, n):\n",
    "            if lines[i][0] != lines[i-1][0]:\n",
    "                maxLines.append(lines[i-1])\n",
    "                minLines.append(lines[i])\n",
    "        maxLines.append(lines[-1])\n",
    "\n",
    "        # 若只有1组，则表明全为平行线\n",
    "        m = len(minLines)\n",
    "        if m <= 1:\n",
    "            return 0\n",
    "\n",
    "        # 右上方角点为（maX, maY), 左下方角点为（miX, miY)\n",
    "        maX, miX, maY, miY = -inf, inf, -inf, inf\n",
    "        for i in range(1, m):\n",
    "            # 每次更新右上方角点时，只计算本组最下方和上一组最上方的直线的交点做更新即可\n",
    "            x, y = getIntersect(minLines[i], maxLines[i-1])\n",
    "            maX = max(x, maX)\n",
    "            maY = max(y, maY) \n",
    "            # 每次更新左下方角点时，只计算本组最上方和上一组最下方的直线的交点做更新即可\n",
    "            x, y = getIntersect(maxLines[i], minLines[i-1])\n",
    "            miX = min(x, miX)\n",
    "            miY = min(y, miY)\n",
    "        return (maX-miX) * (maY - miY)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "############################### 解法一 #################################\n",
    "# 先按照斜率k和b从小到大排序 （时间nlogn）\n",
    "# 再按照斜率的不同分为m组, 每组只有同一斜率最小的b和最大的b（m <= n, 时间n, 空间m~n）\n",
    "# 对m组进行遍历，每一组和上一组进行计算，(时间m~n) 可以证明：\n",
    "# 每次更新右上方角点时，只计算本组最下方和上一组最上方的直线的交点做更新即可\n",
    "# 每次更新左下方角点时，只计算本组最上方和上一组最下方的直线的交点做更新即可\n",
    "# 理论时间O(nlogn + m), 空间O(m)\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        # 求交点的子函数\n",
    "        def getIntersect(line1, line2):\n",
    "            x = (line2[1] - line1[1])/(line1[0] - line2[0])\n",
    "            y = line1[0] * x + line1[1]\n",
    "            return (x, y)\n",
    "        # 按照斜率k和b从小到大排序, 若不多于2条直线返回0\n",
    "        n = len(lines)\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        lines.sort(key=lambda x:(x[0], x[1]))\n",
    "\n",
    "        # 按照斜率的不同分为m组分为m组\n",
    "        # minLines/maxLines记录某一斜率直线组中b最小/大的直线（最上方/最下方的直线）\n",
    "        minLines = [lines[0]]\n",
    "        maxLines = []\n",
    "        for i in range(1, n):\n",
    "            if lines[i][0] != lines[i-1][0]:\n",
    "                maxLines.append(lines[i-1])\n",
    "                minLines.append(lines[i])\n",
    "        maxLines.append(lines[-1])\n",
    "\n",
    "        # 若只有1组，则表明全为平行线\n",
    "        m = len(minLines)\n",
    "        if m <= 1:\n",
    "            return 0\n",
    "\n",
    "        # 右上方角点为（maX, maY), 左下方角点为（miX, miY)\n",
    "        maX, miX, maY, miY = -inf, inf, -inf, inf\n",
    "        for i in range(1, m):\n",
    "            # 每次更新右上方角点时，只计算本组最下方和上一组最上方的直线的交点做更新即可\n",
    "            x, y = getIntersect(minLines[i], maxLines[i-1])\n",
    "            maX = max(x, maX)\n",
    "            maY = max(y, maY) \n",
    "            # 每次更新左下方角点时，只计算本组最上方和上一组最下方的直线的交点做更新即可\n",
    "            x, y = getIntersect(maxLines[i], minLines[i-1])\n",
    "            miX = min(x, miX)\n",
    "            miY = min(y, miY)\n",
    "        return (maX-miX) * (maY - miY)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        n = len(lines)\n",
    "        k = [0] * n\n",
    "        b = [0] * n\n",
    "        lines.sort()\n",
    "        for i in range(n):\n",
    "            k[i] = lines[i][0]\n",
    "            b[i] = lines[i][1]\n",
    "        p = 0\n",
    "        q = 0\n",
    "        while q < n and k[q] == k[p]:\n",
    "            q += 1\n",
    "        if q >= n:\n",
    "            return 0.0\n",
    "        x_min = 1e100\n",
    "        x_max = -1e100\n",
    "        y_min = 1e100\n",
    "        y_max = -1e100\n",
    "        while q < n:\n",
    "            r = q\n",
    "            while r + 1 < n and k[r + 1] == k[q]:\n",
    "                r += 1\n",
    "            cx1 = 1.0 * (b[r] - b[p]) / (k[r] - k[p])\n",
    "            cx2 = 1.0 * (b[q] - b[q - 1]) / (k[q] - k[q - 1])\n",
    "            x_min = min(x_min, min(cx1, cx2))\n",
    "            x_max = max(x_max, max(cx1, cx2))\n",
    "            cy1 = 1.0 * (b[r] * k[p] - b[p] * k[r]) / (k[r] - k[p])\n",
    "            cy2 = 1.0 * (b[q] * k[q - 1] - b[q - 1] * k[q]) / (k[q] - k[q - 1])\n",
    "            y_min = min(y_min, min(cy1, cy2))\n",
    "            y_max = max(y_max, max(cy1, cy2))\n",
    "            p = q\n",
    "            while q < n and k[q] == k[p]:\n",
    "                q += 1\n",
    "        return (x_max - x_min) * (y_max - y_min)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        n = len(lines)\n",
    "        k = [0] * n\n",
    "        b = [0] * n\n",
    "        lines.sort()\n",
    "        for i in range(n):\n",
    "            k[i] = lines[i][0]\n",
    "            b[i] = lines[i][1]\n",
    "        p = 0\n",
    "        q = 0\n",
    "        while q < n and k[q] == k[p]:\n",
    "            q += 1\n",
    "        if q >= n:\n",
    "            return 0.0\n",
    "        x_min = 1e9\n",
    "        x_max = -1e9\n",
    "        y_min = 1e9\n",
    "        y_max = -1e9\n",
    "        while q < n:\n",
    "            r = q\n",
    "            while r + 1 < n and k[r + 1] == k[q]:\n",
    "                r += 1\n",
    "            cx1 = 1.0 * (b[r] - b[p]) / (k[r] - k[p])\n",
    "            cx2 = 1.0 * (b[q] - b[q - 1]) / (k[q] - k[q - 1])\n",
    "            x_min = min(x_min, min(cx1, cx2))\n",
    "            x_max = max(x_max, max(cx1, cx2))\n",
    "            cy1 = 1.0 * (b[r] * k[p] - b[p] * k[r]) / (k[r] - k[p])\n",
    "            cy2 = 1.0 * (b[q] * k[q - 1] - b[q - 1] * k[q]) / (k[q] - k[q - 1])\n",
    "            y_min = min(y_min, min(cy1, cy2))\n",
    "            y_max = max(y_max, max(cy1, cy2))\n",
    "            p = q\n",
    "            while q < n and k[q] == k[p]:\n",
    "                q += 1\n",
    "        return (x_max - x_min) * (y_max - y_min)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        n = len(lines)\n",
    "        k = [0] * n\n",
    "        b = [0] * n\n",
    "        lines.sort()\n",
    "        for i in range(n):\n",
    "            k[i] = lines[i][0]\n",
    "            b[i] = lines[i][1]\n",
    "        p = 0\n",
    "        q = 0\n",
    "        while q < n and k[q] == k[p]:\n",
    "            q += 1\n",
    "        if q >= n:\n",
    "            return 0.0\n",
    "        x_min = 1e9\n",
    "        x_max = -1e9\n",
    "        y_min = 1e9\n",
    "        y_max = -1e9\n",
    "        while q < n:\n",
    "            r = q\n",
    "            while r + 1 < n and k[r + 1] == k[q]:\n",
    "                r += 1\n",
    "            cx1 = 1.0 * (b[r] - b[p]) / (k[r] - k[p])\n",
    "            cx2 = 1.0 * (b[q] - b[q - 1]) / (k[q] - k[q - 1])\n",
    "            x_min = min(x_min, min(cx1, cx2))\n",
    "            x_max = max(x_max, max(cx1, cx2))\n",
    "            cy1 = 1.0 * (b[r] * k[p] - b[p] * k[r]) / (k[r] - k[p])\n",
    "            cy2 = 1.0 * (b[q] * k[q - 1] - b[q - 1] * k[q]) / (k[q] - k[q - 1])\n",
    "            y_min = min(y_min, min(cy1, cy2))\n",
    "            y_max = max(y_max, max(cy1, cy2))\n",
    "            p = q\n",
    "            while q < n and k[q] == k[p]:\n",
    "                q += 1\n",
    "        return (x_max - x_min) * (y_max - y_min)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        n = len(lines)\n",
    "        k = [0] * n\n",
    "        b = [0] * n\n",
    "        lines.sort()\n",
    "        for i in range(n):\n",
    "            k[i] = lines[i][0]\n",
    "            b[i] = lines[i][1]\n",
    "        p = 0\n",
    "        q = 0\n",
    "        while q < n and k[q] == k[p]:\n",
    "            q += 1\n",
    "        if q >= n:\n",
    "            return 0.0\n",
    "        x_min = 1e100\n",
    "        x_max = -1e100\n",
    "        y_min = 1e100\n",
    "        y_max = -1e100\n",
    "        while q < n:\n",
    "            r = q\n",
    "            while r + 1 < n and k[r + 1] == k[q]:\n",
    "                r += 1\n",
    "            cx1 = 1.0 * (b[r] - b[p]) / (k[r] - k[p])\n",
    "            cx2 = 1.0 * (b[q] - b[q - 1]) / (k[q] - k[q - 1])\n",
    "            x_min = min(x_min, min(cx1, cx2))\n",
    "            x_max = max(x_max, max(cx1, cx2))\n",
    "            cy1 = 1.0 * (b[r] * k[p] - b[p] * k[r]) / (k[r] - k[p])\n",
    "            cy2 = 1.0 * (b[q] * k[q - 1] - b[q - 1] * k[q]) / (k[q] - k[q - 1])\n",
    "            y_min = min(y_min, min(cy1, cy2))\n",
    "            y_max = max(y_max, max(cy1, cy2))\n",
    "            p = q\n",
    "            while q < n and k[q] == k[p]:\n",
    "                q += 1\n",
    "        return (x_max - x_min) * (y_max - y_min)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        lines.sort()\n",
    "        count, i, top = [[0]*3 for i in range(10000)], 0, 0\n",
    "        count[0][0], count[0][1] = lines[0][0], 0\n",
    "        for i in range(1, len(lines)):\n",
    "            if lines[i][0] != lines[i-1][0]:\n",
    "                count[top][2] = i-1\n",
    "                top += 1\n",
    "                count[top][0] = lines[i][0]\n",
    "                count[top][1] = i\n",
    "        count[top][2] = len(lines) - 1\n",
    "        if top == 0:\n",
    "            return 0\n",
    "        max_x = (lines[count[0][2]][1] - lines[count[1][1]][1])/(count[1][0] - count[0][0])\n",
    "        min_x = (lines[count[0][1]][1] - lines[count[1][2]][1])/(count[1][0] - count[0][0])\n",
    "        for i in range(1, top):\n",
    "            max_x = max(max_x, (lines[count[i][2]][1] - lines[count[i+1][1]][1])/(count[i+1][0] - count[i][0]))\n",
    "            min_x = min(min_x, (lines[count[i][1]][1] - lines[count[i+1][2]][1])/(count[i+1][0] - count[i][0]))\n",
    "\n",
    "        \n",
    "        max_y = (lines[count[0][2]][1]* count[1][0] - lines[count[1][1]][1]* count[0][0])/(count[1][0] - count[0][0])\n",
    "        min_y = (lines[count[0][1]][1]* count[1][0] - lines[count[1][2]][1]* count[0][0])/(count[1][0] - count[0][0])\n",
    "        for i in range(1,top):\n",
    "            max_y = max(max_y, (lines[count[i][2]][1]* count[i+1][0] - lines[count[i+1][1]][1]* count[i][0])/(count[i+1][0] - count[i][0]))\n",
    "            min_y = min(min_y, (lines[count[i][1]][1]* count[i+1][0] - lines[count[i+1][2]][1]* count[i][0])/(count[i+1][0] - count[i][0]))\n",
    "\n",
    "        return (max_x - min_x) * (max_y - min_y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #数学推导用k，b表示交点的横纵坐标找规律，求解交点横纵坐标的最大最小值然后进行求解。\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        lines.sort()\n",
    "        count, i, top = [[0]*3 for i in range(10000)], 0, 0\n",
    "        count[0][0], count[0][1] = lines[0][0], 0\n",
    "        for i in range(1, len(lines)):\n",
    "            if lines[i][0] != lines[i-1][0]:\n",
    "                count[top][2] = i-1\n",
    "                top += 1\n",
    "                count[top][0] = lines[i][0]\n",
    "                count[top][1] = i\n",
    "        count[top][2] = len(lines) - 1\n",
    "        if top == 0:\n",
    "            return 0\n",
    "        max_x = (lines[count[0][2]][1] - lines[count[1][1]][1])/(count[1][0] - count[0][0])\n",
    "        min_x = (lines[count[0][1]][1] - lines[count[1][2]][1])/(count[1][0] - count[0][0])\n",
    "        for i in range(1, top):\n",
    "            max_x = max(max_x, (lines[count[i][2]][1] - lines[count[i+1][1]][1])/(count[i+1][0] - count[i][0]))\n",
    "            min_x = min(min_x, (lines[count[i][1]][1] - lines[count[i+1][2]][1])/(count[i+1][0] - count[i][0]))\n",
    "\n",
    "        \n",
    "        max_y = (lines[count[0][2]][1]* count[1][0] - lines[count[1][1]][1]* count[0][0])/(count[1][0] - count[0][0])\n",
    "        min_y = (lines[count[0][1]][1]* count[1][0] - lines[count[1][2]][1]* count[0][0])/(count[1][0] - count[0][0])\n",
    "        for i in range(1,top):\n",
    "            max_y = max(max_y, (lines[count[i][2]][1]* count[i+1][0] - lines[count[i+1][1]][1]* count[i][0])/(count[i+1][0] - count[i][0]))\n",
    "            min_y = min(min_y, (lines[count[i][1]][1]* count[i+1][0] - lines[count[i+1][2]][1]* count[i][0])/(count[i+1][0] - count[i][0]))\n",
    "\n",
    "        return (max_x - min_x) * (max_y - min_y)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "#         n = len(lines)\n",
    "#         if n < 2:return 0\n",
    "#         # 上下左右\n",
    "#         res = [-float('Inf'),float('Inf'),float('Inf'),-float('Inf')]\n",
    "#         for i in range(n):\n",
    "#             k,b = lines[i][0],lines[i][1]\n",
    "#             for j in range(i+1,n):\n",
    "#                 k1,b1 = lines[j][0],lines[j][1]\n",
    "#                 if k1 == k:\n",
    "#                     continue\n",
    "#                 x,y = 0,0\n",
    "#                 if b1 == b:\n",
    "#                     x,y = 0,b\n",
    "#                 else:\n",
    "#                     x = -(b1 - b)/(k1 - k)\n",
    "#                     y = x*k + b\n",
    "#                 print([x,y])\n",
    "#                 if res[0] < y:res[0] = y\n",
    "#                 if res[1] > y:res[1] = y\n",
    "#                 if res[2] > x:res[2] = x\n",
    "#                 if res[3] < x:res[3] = x\n",
    "#         if res[0] == res[1] or res[2] == res[3]:return 0\n",
    "#         if res[0] < 0 or res[3] < 0:return 0\n",
    "#         return (res[0] - res[1])*(res[3]-res[2])\n",
    "\n",
    "############################### 解法一 #################################\n",
    "# 先按照斜率k和b从小到大排序 （时间nlogn）\n",
    "# 再按照斜率的不同分为m组, 每组只有同一斜率最小的b和最大的b（m <= n, 时间n, 空间m~n）\n",
    "# 对m组进行遍历，每一组和上一组进行计算，(时间m~n) 可以证明：\n",
    "# 每次更新右上方角点时，只计算本组最下方和上一组最上方的直线的交点做更新即可\n",
    "# 每次更新左下方角点时，只计算本组最上方和上一组最下方的直线的交点做更新即可\n",
    "# 理论时间O(nlogn + m), 空间O(m)\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        # 求交点的子函数\n",
    "        def getIntersect(line1, line2):\n",
    "            x = (line2[1] - line1[1])/(line1[0] - line2[0])\n",
    "            y = line1[0] * x + line1[1]\n",
    "            return (x, y)\n",
    "        # 按照斜率k和b从小到大排序, 若不多于2条直线返回0\n",
    "        n = len(lines)\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        lines.sort(key=lambda x:(x[0], x[1]))\n",
    "\n",
    "        # 按照斜率的不同分为m组分为m组\n",
    "        # minLines/maxLines记录某一斜率直线组中b最小/大的直线（最上方/最下方的直线）\n",
    "        minLines = [lines[0]] # 某一斜率中b最小的直线\n",
    "        maxLines = [] # 某一斜率中b最大的直线\n",
    "        for i in range(1, n):\n",
    "            if lines[i][0] != lines[i-1][0]:\n",
    "                maxLines.append(lines[i-1])\n",
    "                minLines.append(lines[i])\n",
    "        maxLines.append(lines[-1])\n",
    "\n",
    "        # 若只有1组，则表明全为平行线\n",
    "        m = len(minLines)\n",
    "        if m <= 1:\n",
    "            return 0\n",
    "\n",
    "        # 右上方角点为（maX, maY), 左下方角点为（miX, miY)\n",
    "        maX, miX, maY, miY = -inf, inf, -inf, inf\n",
    "        for i in range(1, m):\n",
    "            # 每次更新右上方角点时，只计算本组最下方和上一组最上方的直线的交点做更新即可\n",
    "            x, y = getIntersect(minLines[i], maxLines[i-1])\n",
    "            maX = max(x, maX)\n",
    "            maY = max(y, maY) \n",
    "            # 每次更新左下方角点时，只计算本组最上方和上一组最下方的直线的交点做更新即可\n",
    "            x, y = getIntersect(maxLines[i], minLines[i-1])\n",
    "            miX = min(x, miX)\n",
    "            miY = min(y, miY)\n",
    "        return (maX-miX) * (maY - miY)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        lines.sort()\n",
    "        count, i, top = [[0]*3 for i in range(10000)], 0, 0\n",
    "        count[0][0], count[0][1] = lines[0][0], 0\n",
    "        for i in range(1, len(lines)):\n",
    "            if lines[i][0] != lines[i-1][0]:\n",
    "                count[top][2] = i-1\n",
    "                top += 1\n",
    "                count[top][0] = lines[i][0]\n",
    "                count[top][1] = i\n",
    "        count[top][2] = len(lines) - 1\n",
    "        if top == 0:\n",
    "            return 0\n",
    "        max_x = (lines[count[0][2]][1] - lines[count[1][1]][1])/(count[1][0] - count[0][0])\n",
    "        min_x = (lines[count[0][1]][1] - lines[count[1][2]][1])/(count[1][0] - count[0][0])\n",
    "        for i in range(1, top):\n",
    "            max_x = max(max_x, (lines[count[i][2]][1] - lines[count[i+1][1]][1])/(count[i+1][0] - count[i][0]))\n",
    "            min_x = min(min_x, (lines[count[i][1]][1] - lines[count[i+1][2]][1])/(count[i+1][0] - count[i][0]))\n",
    "\n",
    "        \n",
    "        max_y = (lines[count[0][2]][1]* count[1][0] - lines[count[1][1]][1]* count[0][0])/(count[1][0] - count[0][0])\n",
    "        min_y = (lines[count[0][1]][1]* count[1][0] - lines[count[1][2]][1]* count[0][0])/(count[1][0] - count[0][0])\n",
    "        for i in range(1,top):\n",
    "            max_y = max(max_y, (lines[count[i][2]][1]* count[i+1][0] - lines[count[i+1][1]][1]* count[i][0])/(count[i+1][0] - count[i][0]))\n",
    "            min_y = min(min_y, (lines[count[i][1]][1]* count[i+1][0] - lines[count[i+1][2]][1]* count[i][0])/(count[i+1][0] - count[i][0]))\n",
    "\n",
    "        return (max_x - min_x) * (max_y - min_y)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        lines.sort()\n",
    "        count, i, top = [[0]*3 for i in range(10000)], 0, 0\n",
    "        count[0][0], count[0][1] = lines[0][0], 0\n",
    "        for i in range(1, len(lines)):\n",
    "            if lines[i][0] != lines[i-1][0]:\n",
    "                count[top][2] = i-1\n",
    "                top += 1\n",
    "                count[top][0] = lines[i][0]\n",
    "                count[top][1] = i\n",
    "        count[top][2] = len(lines) - 1\n",
    "        if top == 0:\n",
    "            return 0\n",
    "        max_x = (lines[count[0][2]][1] - lines[count[1][1]][1])/(count[1][0] - count[0][0])\n",
    "        min_x = (lines[count[0][1]][1] - lines[count[1][2]][1])/(count[1][0] - count[0][0])\n",
    "        for i in range(1, top):\n",
    "            max_x = max(max_x, (lines[count[i][2]][1] - lines[count[i+1][1]][1])/(count[i+1][0] - count[i][0]))\n",
    "            min_x = min(min_x, (lines[count[i][1]][1] - lines[count[i+1][2]][1])/(count[i+1][0] - count[i][0]))\n",
    "\n",
    "        \n",
    "        max_y = (lines[count[0][2]][1]* count[1][0] - lines[count[1][1]][1]* count[0][0])/(count[1][0] - count[0][0])\n",
    "        min_y = (lines[count[0][1]][1]* count[1][0] - lines[count[1][2]][1]* count[0][0])/(count[1][0] - count[0][0])\n",
    "        for i in range(1,top):\n",
    "            max_y = max(max_y, (lines[count[i][2]][1]* count[i+1][0] - lines[count[i+1][1]][1]* count[i][0])/(count[i+1][0] - count[i][0]))\n",
    "            min_y = min(min_y, (lines[count[i][1]][1]* count[i+1][0] - lines[count[i+1][2]][1]* count[i][0])/(count[i+1][0] - count[i][0]))\n",
    "\n",
    "        return (max_x - min_x) * (max_y - min_y)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        lines.sort()\n",
    "        count, i, top = [[0]*3 for i in range(10000)], 0, 0\n",
    "        count[0][0], count[0][1] = lines[0][0], 0\n",
    "        for i in range(1, len(lines)):\n",
    "            if lines[i][0] != lines[i-1][0]:\n",
    "                count[top][2] = i-1\n",
    "                top += 1\n",
    "                count[top][0] = lines[i][0]\n",
    "                count[top][1] = i\n",
    "        count[top][2] = len(lines) - 1\n",
    "        if top == 0:\n",
    "            return 0\n",
    "        max_x = (lines[count[0][2]][1] - lines[count[1][1]][1])/(count[1][0] - count[0][0])\n",
    "        min_x = (lines[count[0][1]][1] - lines[count[1][2]][1])/(count[1][0] - count[0][0])\n",
    "        for i in range(1, top):\n",
    "            max_x = max(max_x, (lines[count[i][2]][1] - lines[count[i+1][1]][1])/(count[i+1][0] - count[i][0]))\n",
    "            min_x = min(min_x, (lines[count[i][1]][1] - lines[count[i+1][2]][1])/(count[i+1][0] - count[i][0]))\n",
    "\n",
    "        \n",
    "        max_y = (lines[count[0][2]][1]* count[1][0] - lines[count[1][1]][1]* count[0][0])/(count[1][0] - count[0][0])\n",
    "        min_y = (lines[count[0][1]][1]* count[1][0] - lines[count[1][2]][1]* count[0][0])/(count[1][0] - count[0][0])\n",
    "        for i in range(1,top):\n",
    "            max_y = max(max_y, (lines[count[i][2]][1]* count[i+1][0] - lines[count[i+1][1]][1]* count[i][0])/(count[i+1][0] - count[i][0]))\n",
    "            min_y = min(min_y, (lines[count[i][1]][1]* count[i+1][0] - lines[count[i+1][2]][1]* count[i][0])/(count[i+1][0] - count[i][0]))\n",
    "\n",
    "        return (max_x - min_x) * (max_y - min_y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        #copy\n",
    "        d = defaultdict(list)\n",
    "        for line in lines:\n",
    "            d[line[0]].append(line[1])\n",
    "\n",
    "        xs,ys=[],[]\n",
    "        def intersect(f,g):\n",
    "            xs.append(x:=(g[1]-f[1])/(f[0]-g[0]))\n",
    "            ys.append(y:=f[0]*x+f[1])\n",
    "        \n",
    "        k = sorted(d.keys())\n",
    "        for i,j in zip(k[:-1],k[1:]):\n",
    "            intersect((i,min(d[i])),(j,max(d[j])))\n",
    "            intersect((i,max(d[i])),(j,min(d[j])))\n",
    "        return (max(xs)-min(xs))*(max(ys)-min(ys)) if xs else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        if len(lines) <= 2:\n",
    "            return 0\n",
    "        dic = {}\n",
    "        for k, b in lines:\n",
    "            if k in dic:\n",
    "                dic[k][0] = min(dic[k][0], b)\n",
    "                dic[k][1] = max(dic[k][1], b)\n",
    "            else:\n",
    "                dic[k] = [b, b]\n",
    "        if len(dic) == 1:\n",
    "            return 0\n",
    "        ks = sorted(dic.keys())\n",
    "        n = len(ks)\n",
    "        min_x = min_y = float('inf')\n",
    "        max_x = max_y = float('-inf')\n",
    "        for i in range(1, n):\n",
    "            k1 = ks[i-1]\n",
    "            min_b1, max_b1 = dic[k1]\n",
    "            k2 = ks[i]\n",
    "            min_b2, max_b2 = dic[k2]\n",
    "            diff_k = k1 - k2\n",
    "            min_x = min(min_x, (max_b2 - min_b1) / diff_k)\n",
    "            max_x = max(max_x, (min_b2 - max_b1) / diff_k)\n",
    "            min_y = min(min_y, (k1 * max_b2 - k2 * min_b1) / diff_k)\n",
    "            max_y = max(max_y, (k1 * min_b2 - k2 * max_b1) / diff_k)\n",
    "        return (max_x - min_x) * (max_y - min_y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        if len(lines) <= 2:\n",
    "            return 0\n",
    "        dic = {}\n",
    "        for k, b in lines:\n",
    "            if k in dic:\n",
    "                dic[k][0] = min(dic[k][0], b)\n",
    "                dic[k][1] = max(dic[k][1], b)\n",
    "            else:\n",
    "                dic[k] = [b, b]\n",
    "        if len(dic) == 1:\n",
    "            return 0\n",
    "        ks = sorted(dic.keys())\n",
    "        n = len(ks)\n",
    "        min_x = min_y = float('inf')\n",
    "        max_x = max_y = float('-inf')\n",
    "        for i in range(1, n):\n",
    "            k1 = ks[i-1]\n",
    "            min_b1, max_b1 = dic[k1]\n",
    "            k2 = ks[i]\n",
    "            min_b2, max_b2 = dic[k2]\n",
    "            diff_k = k1 - k2\n",
    "            min_x = min(min_x, (max_b2 - min_b1) / diff_k)\n",
    "            max_x = max(max_x, (min_b2 - max_b1) / diff_k)\n",
    "            min_y = min(min_y, (k1 * max_b2 - k2 * min_b1) / diff_k)\n",
    "            max_y = max(max_y, (k1 * min_b2 - k2 * max_b1) / diff_k)\n",
    "        return (max_x - min_x) * (max_y - min_y)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        Max = 1e9\n",
    "        Times = 50\n",
    "\n",
    "        #k sort\n",
    "        lines.sort(key=lambda x:(x[0], x[1]))\n",
    "\n",
    "        #rightest point\n",
    "        left = -Max\n",
    "        right = Max\n",
    "        middle = (left + right)/2\n",
    "        theRightest = middle\n",
    "        for i in range(Times):\n",
    "            for j in range(len(lines)-1):\n",
    "                if lines[j][0]*middle+lines[j][1] > lines[j+1][0]*middle+lines[j+1][1]:\n",
    "                    left = middle\n",
    "                    middle = (left + right)/2\n",
    "                    break;\n",
    "                elif j == len(lines) - 2:\n",
    "                    right = middle\n",
    "                    middle = (left + right)/2\n",
    "        theRightest = middle\n",
    "        \n",
    "        #the Highest\n",
    "        low = -Max\n",
    "        up = Max\n",
    "        middle = (up + low)/2\n",
    "        theHighest = middle\n",
    "        for i in range(Times):\n",
    "            for j in range(len(lines)-1):\n",
    "                if (middle-lines[j][1])/lines[j][0] < (middle-lines[j+1][1])/lines[j+1][0]:\n",
    "                    low = middle\n",
    "                    middle = (up + low)/2\n",
    "                    break;\n",
    "                elif j == len(lines) - 2:\n",
    "                    up = middle\n",
    "                    middle = (up + low)/2\n",
    "        theHighest = middle\n",
    "\n",
    "        lines.sort(key=lambda x:(x[0], -x[1]))\n",
    "        \n",
    "        #leftest point\n",
    "        left = -Max\n",
    "        right = Max\n",
    "        middle = (left + right)/2\n",
    "        theLeftest = middle\n",
    "        for i in range(Times):\n",
    "            for j in range(len(lines)-1):\n",
    "                if lines[j][0]*middle+lines[j][1] < lines[j+1][0]*middle+lines[j+1][1]:\n",
    "                    right = middle\n",
    "                    middle = (left + right)/2\n",
    "                    break;\n",
    "                elif j == len(lines) - 2:\n",
    "                    left = middle\n",
    "                    middle = (left + right)/2\n",
    "        theLeftest = middle\n",
    "\n",
    "        #the lowest\n",
    "        low = -Max\n",
    "        up = Max\n",
    "        middle = (up + low)/2\n",
    "        theLowest = middle\n",
    "        for i in range(Times):\n",
    "            for j in range(len(lines)-1):\n",
    "                if (middle-lines[j][1])/lines[j][0] > (middle-lines[j+1][1])/lines[j+1][0]:\n",
    "                    up = middle\n",
    "                    middle = (up + low)/2\n",
    "                    break;\n",
    "                elif j == len(lines) - 2:\n",
    "                    low = middle\n",
    "                    middle = (up + low)/2\n",
    "        theLowest = middle\n",
    "\n",
    "        if theHighest - theLowest < 1e-8 or theRightest - theLeftest < 1e-8:\n",
    "            return 0;\n",
    "        return (theHighest - theLowest)*(theRightest - theLeftest)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        def update(k1, k2, b1, b2, x_min, x_max,y_min, y_max):\n",
    "            x = (b2 - b1) / (k1 - k2)\n",
    "            y = k1 * x +b1\n",
    "            x_min = min(x_min, x)\n",
    "            x_max = max(x_max, x)        \n",
    "            y_min = min(y_min, y)\n",
    "            y_max = max(y_max, y)\n",
    "            return x_min, x_max, y_min, y_max\n",
    "\n",
    "        if len(lines) == 1: return 0\n",
    "        x_max = y_max = float('-inf')\n",
    "        y_min = x_min = float('inf')\n",
    "        dic = {}\n",
    "        for i in lines:\n",
    "            if i[0] in dic.keys():\n",
    "                dic[i[0]].append(i[1])\n",
    "                dic[i[0]] = [max(dic[i[0]]), min(dic[i[0]])]\n",
    "            else:\n",
    "                dic[i[0]] = [i[1]]\n",
    "        l = sorted(list(dic.keys()))\n",
    "        if len(l) == 1: return 0\n",
    "        print(dic)\n",
    "        for i in range(len(l) - 1):\n",
    "            for b1 in dic[l[i]]:\n",
    "                for b2 in dic[l[i + 1]]:\n",
    "                    x_min, x_max, y_min, y_max = update(l[i], l[i + 1], b1, b2, x_min, x_max, y_min, y_max)\n",
    "        for b1 in dic[l[-1]]:\n",
    "            for b2 in dic[l[0]]:\n",
    "                x_min, x_max, y_min, y_max = update(l[-1], l[0], b1, b2, x_min, x_max, y_min, y_max)\n",
    "        if x_max == float('-inf'):\n",
    "            return 0\n",
    "        return (y_max - y_min) * (x_max - x_min)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "INF = 10**9\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        n = len(lines)\n",
    "        lines = sorted(lines, key = lambda x: (x[0], x[1]), reverse = True)\n",
    "        if all(lines[i][0] == lines[i+1][0] for i in range(n - 1)):\n",
    "            return 0.0\n",
    "\n",
    "        def rightsort(x: float, sig) -> bool:\n",
    "            if sig == '+x':\n",
    "                for i in range(n - 1):\n",
    "                    if x * lines[i][0] + lines[i][1] < x * lines[i + 1][0] + lines[i + 1][1]:\n",
    "                        return False\n",
    "                return True\n",
    "            if sig == '-x':\n",
    "                for i in range(n - 1):\n",
    "                    if x * lines[i][0] + lines[i][1] > x * lines[i + 1][0] + lines[i + 1][1]:\n",
    "                        return False\n",
    "                return True\n",
    "            if sig == '+y':\n",
    "                for i in range(n - 1):\n",
    "                    if (x - lines[i][1]) / lines[i][0] > (x - lines[i+1][1]) / lines[i+1][0]:\n",
    "                        return False\n",
    "                return True\n",
    "            if sig == '-y':\n",
    "                for i in range(n - 1):\n",
    "                    if (x - lines[i][1]) / lines[i][0] < (x - lines[i+1][1]) / lines[i+1][0]:\n",
    "                        return False\n",
    "                return True\n",
    "\n",
    "        l1, r1 = -1*INF, INF\n",
    "        eplison = 10 ** (-4)\n",
    "        while l1 < r1 - eplison:\n",
    "            mid = (l1 + r1) / 2\n",
    "            if rightsort(mid, '+x'):\n",
    "                r1 = mid\n",
    "            else:\n",
    "                l1 = mid\n",
    "        mx = l1\n",
    "        \n",
    "        l3, r3 = -1*INF, INF\n",
    "        while l3 < r3 - eplison:\n",
    "            mid = (l3 + r3) / 2\n",
    "            if rightsort(mid, '+y'):\n",
    "                r3 = mid\n",
    "            else:\n",
    "                l3 = mid\n",
    "        my = l3\n",
    "\n",
    "        lines = sorted(lines, key = lambda x: (x[0], -x[1]), reverse = True)\n",
    "        l2, r2 = -1*INF, INF\n",
    "        while l2 < r2 - eplison:\n",
    "            mid = (l2 + r2) / 2\n",
    "            if rightsort(mid, '-x'):\n",
    "                l2 = mid\n",
    "            else:\n",
    "                r2 = mid\n",
    "        nx = r2\n",
    "\n",
    "        l4, r4 = -1*INF, INF\n",
    "        while l4 < r4 - eplison:\n",
    "            mid = (l4 + r4) / 2\n",
    "            if rightsort(mid, '-y'):\n",
    "                l4 = mid\n",
    "            else:\n",
    "                r4 = mid\n",
    "        ny = r4\n",
    "\n",
    "        # print(mx, nx, my, ny)\n",
    "        return (mx -nx) * (my - ny)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "INF = 10**9\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        n = len(lines)\n",
    "        lines = sorted(lines, key = lambda x: (x[0], x[1]), reverse = True)\n",
    "        if all(lines[i][0] == lines[i+1][0] for i in range(n - 1)):\n",
    "            return 0.0\n",
    "\n",
    "        def rightsort(x: float, sig) -> bool:\n",
    "            if sig == '+x':\n",
    "                for i in range(n - 1):\n",
    "                    if x * lines[i][0] + lines[i][1] < x * lines[i + 1][0] + lines[i + 1][1]:\n",
    "                        return False\n",
    "                return True\n",
    "            if sig == '-x':\n",
    "                for i in range(n - 1):\n",
    "                    if x * lines[i][0] + lines[i][1] > x * lines[i + 1][0] + lines[i + 1][1]:\n",
    "                        return False\n",
    "                return True\n",
    "            if sig == '+y':\n",
    "                for i in range(n - 1):\n",
    "                    if (x - lines[i][1]) / lines[i][0] > (x - lines[i+1][1]) / lines[i+1][0]:\n",
    "                        return False\n",
    "                return True\n",
    "            if sig == '-y':\n",
    "                for i in range(n - 1):\n",
    "                    if (x - lines[i][1]) / lines[i][0] < (x - lines[i+1][1]) / lines[i+1][0]:\n",
    "                        return False\n",
    "                return True\n",
    "\n",
    "        l1, r1 = -1*INF, INF\n",
    "        eplison = 10 ** (-5)\n",
    "        while l1 < r1 - eplison:\n",
    "            mid = (l1 + r1) / 2\n",
    "            if rightsort(mid, '+x'):\n",
    "                r1 = mid\n",
    "            else:\n",
    "                l1 = mid\n",
    "        mx = l1\n",
    "        \n",
    "        l3, r3 = -1*INF, INF\n",
    "        while l3 < r3 - eplison:\n",
    "            mid = (l3 + r3) / 2\n",
    "            if rightsort(mid, '+y'):\n",
    "                r3 = mid\n",
    "            else:\n",
    "                l3 = mid\n",
    "        my = l3\n",
    "\n",
    "        lines = sorted(lines, key = lambda x: (x[0], -x[1]), reverse = True)\n",
    "        l2, r2 = -1*INF, INF\n",
    "        while l2 < r2 - eplison:\n",
    "            mid = (l2 + r2) / 2\n",
    "            if rightsort(mid, '-x'):\n",
    "                l2 = mid\n",
    "            else:\n",
    "                r2 = mid\n",
    "        nx = r2\n",
    "\n",
    "        l4, r4 = -1*INF, INF\n",
    "        while l4 < r4 - eplison:\n",
    "            mid = (l4 + r4) / 2\n",
    "            if rightsort(mid, '-y'):\n",
    "                l4 = mid\n",
    "            else:\n",
    "                r4 = mid\n",
    "        ny = r4\n",
    "\n",
    "        # print(mx, nx, my, ny)\n",
    "        return (mx -nx) * (my - ny)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "INF = 10**9\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        n = len(lines)\n",
    "        lines = sorted(lines, key = lambda x: (x[0], x[1]), reverse = True)\n",
    "        if all(lines[i][0] == lines[i+1][0] for i in range(n - 1)):\n",
    "            return 0.0\n",
    "\n",
    "        def rightsort(x: float, sig) -> bool:\n",
    "            if sig == '+x':\n",
    "                for i in range(n - 1):\n",
    "                    if x * lines[i][0] + lines[i][1] < x * lines[i + 1][0] + lines[i + 1][1]:\n",
    "                        return False\n",
    "                return True\n",
    "            if sig == '-x':\n",
    "                for i in range(n - 1):\n",
    "                    if x * lines[i][0] + lines[i][1] > x * lines[i + 1][0] + lines[i + 1][1]:\n",
    "                        return False\n",
    "                return True\n",
    "            if sig == '+y':\n",
    "                for i in range(n - 1):\n",
    "                    if (x - lines[i][1]) / lines[i][0] > (x - lines[i+1][1]) / lines[i+1][0]:\n",
    "                        return False\n",
    "                return True\n",
    "            if sig == '-y':\n",
    "                for i in range(n - 1):\n",
    "                    if (x - lines[i][1]) / lines[i][0] < (x - lines[i+1][1]) / lines[i+1][0]:\n",
    "                        return False\n",
    "                return True\n",
    "\n",
    "        l1, r1 = -1*INF, INF\n",
    "        eplison = 10 ** (-4)\n",
    "        while l1 < r1 - eplison:\n",
    "            mid = (l1 + r1) / 2\n",
    "            if rightsort(mid, '+x'):\n",
    "                r1 = mid\n",
    "            else:\n",
    "                l1 = mid\n",
    "        mx = l1\n",
    "        \n",
    "        l3, r3 = -1*INF, INF\n",
    "        while l3 < r3 - eplison:\n",
    "            mid = (l3 + r3) / 2\n",
    "            if rightsort(mid, '+y'):\n",
    "                r3 = mid\n",
    "            else:\n",
    "                l3 = mid\n",
    "        my = l3\n",
    "\n",
    "        lines = sorted(lines, key = lambda x: (x[0], -x[1]), reverse = True)\n",
    "        l2, r2 = -1*INF, INF\n",
    "        while l2 < r2 - eplison:\n",
    "            mid = (l2 + r2) / 2\n",
    "            if rightsort(mid, '-x'):\n",
    "                l2 = mid\n",
    "            else:\n",
    "                r2 = mid\n",
    "        nx = r2\n",
    "\n",
    "        l4, r4 = -1*INF, INF\n",
    "        while l4 < r4 - eplison:\n",
    "            mid = (l4 + r4) / 2\n",
    "            if rightsort(mid, '-y'):\n",
    "                l4 = mid\n",
    "            else:\n",
    "                r4 = mid\n",
    "        ny = r4\n",
    "\n",
    "        # print(mx, nx, my, ny)\n",
    "        return (mx -nx) * (my - ny)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "INF = 10**9\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        n = len(lines)\n",
    "        lines = sorted(lines, key = lambda x: (x[0], x[1]), reverse = True)\n",
    "        if all(lines[i][0] == lines[i+1][0] for i in range(n - 1)):\n",
    "            return 0.0\n",
    "\n",
    "        def rightsort(x: float, sig) -> bool:\n",
    "            if sig == '+x':\n",
    "                for i in range(n - 1):\n",
    "                    if x * lines[i][0] + lines[i][1] < x * lines[i + 1][0] + lines[i + 1][1]:\n",
    "                        return False\n",
    "                return True\n",
    "            if sig == '-x':\n",
    "                for i in range(n - 1):\n",
    "                    if x * lines[i][0] + lines[i][1] > x * lines[i + 1][0] + lines[i + 1][1]:\n",
    "                        return False\n",
    "                return True\n",
    "            if sig == '+y':\n",
    "                for i in range(n - 1):\n",
    "                    if (x - lines[i][1]) / lines[i][0] > (x - lines[i+1][1]) / lines[i+1][0]:\n",
    "                        return False\n",
    "                return True\n",
    "            if sig == '-y':\n",
    "                for i in range(n - 1):\n",
    "                    if (x - lines[i][1]) / lines[i][0] < (x - lines[i+1][1]) / lines[i+1][0]:\n",
    "                        return False\n",
    "                return True\n",
    "\n",
    "        l1, r1 = -1*INF, INF\n",
    "        eplison = 10 ** (-6)\n",
    "        while l1 < r1 - eplison:\n",
    "            mid = (l1 + r1) / 2\n",
    "            if rightsort(mid, '+x'):\n",
    "                r1 = mid\n",
    "            else:\n",
    "                l1 = mid\n",
    "        mx = l1\n",
    "        \n",
    "        l3, r3 = -1*INF, INF\n",
    "        while l3 < r3 - eplison:\n",
    "            mid = (l3 + r3) / 2\n",
    "            if rightsort(mid, '+y'):\n",
    "                r3 = mid\n",
    "            else:\n",
    "                l3 = mid\n",
    "        my = l3\n",
    "\n",
    "        lines = sorted(lines, key = lambda x: (x[0], -x[1]), reverse = True)\n",
    "        l2, r2 = -1*INF, INF\n",
    "        while l2 < r2 - eplison:\n",
    "            mid = (l2 + r2) / 2\n",
    "            if rightsort(mid, '-x'):\n",
    "                l2 = mid\n",
    "            else:\n",
    "                r2 = mid\n",
    "        nx = r2\n",
    "\n",
    "        l4, r4 = -1*INF, INF\n",
    "        while l4 < r4 - eplison:\n",
    "            mid = (l4 + r4) / 2\n",
    "            if rightsort(mid, '-y'):\n",
    "                l4 = mid\n",
    "            else:\n",
    "                r4 = mid\n",
    "        ny = r4\n",
    "\n",
    "        print(mx, nx, my, ny)\n",
    "        return (mx -nx) * (my - ny)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef minRecSize(self, lines):\n",
    "\t\tmaxY = self.calc(lines, False)\n",
    "\t\tminY = -self.calc([[k, -b] for k, b in lines], False)\n",
    "\t\tmaxX = self.calc([[k, -b / k] for k, b in lines], True)\n",
    "\t\tminX = -self.calc([[k, b / k] for k, b in lines], True)\n",
    "\t\tans = (maxX - minX) * (maxY - minY)\n",
    "\t\treturn 0 if ans == float('inf') else ans\n",
    "\t\t\n",
    "\tdef calc(self, lines, flag):\n",
    "\t\tlines.sort(reverse = flag)\n",
    "\t\tn = len(lines)\n",
    "\t\tres = float('-inf')\n",
    "\t\tidx = 0\n",
    "\t\tpool = []\n",
    "\t\twhile idx < n:\n",
    "\t\t\tk = lines[idx][0] #直接用倒数有精度问题，下面的等于判断不准确\n",
    "\t\t\tminB = lines[idx][1]\n",
    "\t\t\tmaxB = lines[idx][1]\n",
    "\t\t\twhile idx < n and lines[idx][0] == k:\n",
    "\t\t\t\tminB = min(minB, lines[idx][1])\n",
    "\t\t\t\tmaxB = max(maxB, lines[idx][1])\n",
    "\t\t\t\tidx += 1\n",
    "\t\t\tk0 = 1 / k if flag else k\n",
    "\t\t\tif len(pool) == 0:\n",
    "\t\t\t\tpool.append([k0, maxB, float('-inf'), float('inf')])\n",
    "\t\t\telse:\n",
    "\t\t\t\ti, x, y = self.bs(pool, k0, minB, 0, len(pool))\n",
    "\t\t\t\tres = max(res, y)\n",
    "\t\t\t\ti, x, y = self.bs(pool, k0, maxB, 0, len(pool))\n",
    "\t\t\t\tif pool[i][2] == x:\n",
    "\t\t\t\t\ti -= 1\n",
    "\t\t\t\tpool[i][3] = x\n",
    "\t\t\t\tpool = pool[:i + 1] + [[k0, maxB, x, float('inf')]]\n",
    "\t\treturn res\n",
    "\t\n",
    "\tdef bs(self, pool, k, b, l, r):\n",
    "\t\tm = (l + r) >> 1\n",
    "\t\tk1, b1 = pool[m][0], pool[m][1]\n",
    "\t\tx = round((b - b1) / (k1 - k), 9)\n",
    "\t\tif pool[m][2] <= x <= pool[m][3]:\n",
    "\t\t\treturn m, x, round(k * x + b, 9)\n",
    "\t\tif x > pool[m][3]:\n",
    "\t\t\treturn self.bs(pool, k, b, m + 1, r)\n",
    "\t\telse:\n",
    "\t\t\treturn self.bs(pool, k, b, l, m - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "\n",
    "T = 50\n",
    "INF = float(1e9)\n",
    "\n",
    "class Solution:\n",
    "    def minRecSize(self, lines):\n",
    "        n = len(lines)\n",
    "        if n == 1:\n",
    "            return 0.0\n",
    "        \n",
    "        lines.sort(key=lambda x: (x[0], x[1]))\n",
    "        rl, rr = -INF, INF\n",
    "        for _ in range(T):\n",
    "            mid = (rl + rr) / 2\n",
    "            conflict = False\n",
    "            for i in range(n - 1):\n",
    "                a = lines[i][0] * mid + lines[i][1]\n",
    "                b = lines[i + 1][0] * mid + lines[i + 1][1]\n",
    "                if a - b > 1e-8:\n",
    "                    conflict = True\n",
    "                    break\n",
    "            if conflict:\n",
    "                rl = mid\n",
    "            else:\n",
    "                rr = mid\n",
    "        \n",
    "        lines.sort(key=lambda x: (-x[0], x[1]))\n",
    "        ll, lr = -INF, INF\n",
    "        for _ in range(T):\n",
    "            mid = (ll + lr) / 2\n",
    "            conflict = False\n",
    "            for i in range(n - 1):\n",
    "                a = lines[i][0] * mid + lines[i][1]\n",
    "                b = lines[i + 1][0] * mid + lines[i + 1][1]\n",
    "                if a - b > 1e-8:\n",
    "                    conflict = True\n",
    "                    break\n",
    "            if conflict:\n",
    "                lr = mid\n",
    "            else:\n",
    "                ll = mid\n",
    "                \n",
    "        lines.sort(key=lambda x: (-x[0], -x[1]))\n",
    "        ul, ur = -INF, INF\n",
    "        for _ in range(T):\n",
    "            mid = (ul + ur) / 2\n",
    "            conflict = False\n",
    "            for i in range(n - 1):\n",
    "                a = (mid - lines[i][1]) / lines[i][0]\n",
    "                b = (mid - lines[i + 1][1]) / lines[i + 1][0]\n",
    "                if a - b > 1e-8:\n",
    "                    conflict = True\n",
    "                    break\n",
    "            if conflict:\n",
    "                ul = mid\n",
    "            else:\n",
    "                ur = mid\n",
    "                \n",
    "        lines.sort(key=lambda x: (x[0], -x[1]))\n",
    "        dl, dr = -INF, INF\n",
    "        for _ in range(T):\n",
    "            mid = (dl + dr) / 2\n",
    "            conflict = False\n",
    "            for i in range(n - 1):\n",
    "                a = (mid - lines[i][1]) / lines[i][0]\n",
    "                b = (mid - lines[i + 1][1]) / lines[i + 1][0]\n",
    "                if a - b > 1e-8:\n",
    "                    conflict = True\n",
    "                    break\n",
    "            if conflict:\n",
    "                dr = mid\n",
    "            else:\n",
    "                dl = mid\n",
    "                \n",
    "        if ll - rr > 1e-8:\n",
    "            return 0.0\n",
    "        \n",
    "        return (rr - ll) * (ur - dl)\n",
    "\n",
    "# Test example\n",
    "solution = Solution()\n",
    "print(solution.minRecSize([[1, 1], [2, 2], [3, 3]]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRecSize(self, lines: List[List[int]]) -> float:\n",
    "        \n",
    "        # 2023.08.24 Thu\n",
    "        # # initialize the four points that will determine the matrix size\n",
    "        # x_left = None\n",
    "        # x_right = None\n",
    "        # y_top = None\n",
    "        # y_bottom = None\n",
    "\n",
    "        # # count the cross point\n",
    "        # num_point = 0\n",
    "\n",
    "        # if len(lines) == 1:  # if there is only one line\n",
    "        #     return 0\n",
    "        # else:\n",
    "        #     # calculate the possible cross point between any two lines\n",
    "        #     for i in range(len(lines)-1):  # the fixed line\n",
    "        #         for j in range(i+1, len(lines)):\n",
    "        #             if lines[i][0] == lines[j][0]:  # parallel\n",
    "        #                 continue\n",
    "        #             else:\n",
    "        #                 x = - (lines[i][1] - lines[j][1]) / (lines[i][0] - lines[j][0])\n",
    "        #                 y = (lines[i][0] * lines[j][1] - lines[i][1] * lines[j][0]) / (lines[i][0] - lines[j][0])\n",
    "        #                 num_point += 1\n",
    "        #                 if num_point == 1:  # initialize\n",
    "        #                     x_left = x_right = x\n",
    "        #                     y_top = y_bottom = y\n",
    "        #                 else:  # compare\n",
    "        #                     if x < x_left:\n",
    "        #                         x_left = x\n",
    "        #                     elif x > x_right:\n",
    "        #                         x_right = x\n",
    "        #                     if y < y_bottom:\n",
    "        #                         y_bottom = y\n",
    "        #                     elif y > y_top:\n",
    "        #                         y_top = y\n",
    "            \n",
    "        #     if num_point == 1 or num_point == 0:\n",
    "        #         return 0\n",
    "        #     else:\n",
    "        #         return (x_right - x_left) * (y_top - y_bottom)\n",
    "\n",
    "        # 2023.08.24 Fri\n",
    "\n",
    "        from fractions import Fraction\n",
    "        Xmin, Ymin = float('inf'), float('inf')\n",
    "        Xmax, Ymax = float('-inf'), float('-inf')\n",
    "        mxk = collections.defaultdict(list)\n",
    "        myk = collections.defaultdict(list)\n",
    "        for k, b in lines:\n",
    "            mxk[k].append(b)\n",
    "            if k != 0:\n",
    "                myk[Fraction(1, k)].append(Fraction(b, k))\n",
    "            else:\n",
    "                Ymin = min(b, Ymin)\n",
    "                Ymax = max(b, Ymax)\n",
    "        lix, liy = sorted(mxk), sorted(myk)\n",
    "        for i in range(1, len(lix)):\n",
    "            kj, ki = lix[i - 1], lix[i]\n",
    "            bj_max, bj_min = max(mxk[kj]), min(mxk[kj])\n",
    "            bi_max, bi_min = max(mxk[ki]), min(mxk[ki])\n",
    "            x1, x2 = -(bi_min - bj_max) / (ki - kj), -(bi_max - bj_min) / (ki - kj)\n",
    "            Xmax, Xmin = max(x1, x2, Xmax), min(x1, x2, Xmin)\n",
    "        for i in range(1, len(liy)):\n",
    "            kj, ki = liy[i - 1], liy[i]\n",
    "            bj_max, bj_min = max(myk[kj]), min(myk[kj])\n",
    "            bi_max, bi_min = max(myk[ki]), min(myk[ki])\n",
    "            y1, y2 = (bi_min - bj_max) / (ki - kj), (bi_max - bj_min) / (ki - kj)\n",
    "            Ymax, Ymin = max(y1, y2, Ymax), min(y1, y2, Ymin)\n",
    "        ans=(Ymax-Ymin)*(Xmax-Xmin)\n",
    "        return ans if ans!=float('inf') else 0"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
